// 78. 子集
// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
var subSets = function(nums){
    let res = [];
    let path = [];
    backTrack(nums, res, path, 0);
    return res;
}

function backTrack(nums, res, path, start){
    res.push([...path]);
    for(let i = start; i< nums.length; i++){
        path.push(nums[i]);
        backTrack(nums, res, path, i+1);
        path.pop();
    }
}



// 90. 子集 II
// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
// 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 
var subsetsWithDup = function(nums) {
    let res = [];
    let path = [];
    nums.sort((a, b) => a-b);
    backTrack(nums, res, path, 0);
    return res;
};

function backTrack(nums, res, path, start){
    res.push([...path]);
    for(let i = start; i<nums.length; i++){
        // 跳过重复部分
        if(i>start && nums[i] === nums[i-1]) continue;
        path.push(nums[i]);
        backTrack(nums, res, path, i+1);
        path.pop();
    }
}

// 40. 组合总和 II

// 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的每个数字在每个组合中只能使用 一次 。
// 注意：解集不能包含重复的组合。

var combinationSum2 = function(candidates, target) {
  let res = [];
  let path = [];
  let sumTrack = 0;
  candidates.sort((a, b) => a - b);
  backTrack(candidates, path, res, 0, target, sumTrack);
  return res;

};

function backTrack (nums, path, res, start, target, sumTrack) {
    if (sumTrack === target) {
        res.push([...path]);
        return;
    }
    if (sumTrack > target) return;
    for (let i = start; i < nums.length; i++) {
        if (i > start && nums[i] === nums[i - 1]) continue;
        path.push(nums[i]);
        sumTrack += nums[i];
        backTrack(nums, path, res, i + 1, target, sumTrack);
        path.pop();
        sumTrack -= nums[i];
  }
}

// 39. 组合总和
// 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
// candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
var combinationSum = function(candidates, target) {
  let res = [];
  let path = [];
  let sumTrack = 0;
  backTrack(candidates, path, res, 0, target, sumTrack);
  return res;

};

function backTrack (nums, path, res, start, target, sumTrack) {
    if (sumTrack === target) {
        res.push([...path]);
        return;
    }
    if (sumTrack > target) return;
    for (let i = start; i < nums.length; i++) {
        path.push(nums[i]);
        sumTrack += nums[i];
        backTrack(nums, path, res, i, target, sumTrack);
        path.pop();
        sumTrack -= nums[i];
    }
}

// 46. 全排列

// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

var permute = function(nums) {
    let res = [];
    let path = [];
    let visited = [];
    backTrack(nums, res, path, visited);
    return res;
};

function backTrack(nums, res, path, visited){
    if(path.length === nums.length) {
        res.push([...path]);
        return;
    }
    for(let i = 0; i<nums.length; i++){
        if(visited[i]) continue;
        path.push(nums[i]);
        visited[i] = true;
        backTrack(nums, res, path, visited);
        path.pop();
        visited[i] = false;
    }
}

// 47. 全排列 II

// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

var permuteUnique = function(nums) {
    let res = [];
    let path = [];
    let visited = [];
    nums.sort((a,b)=>a-b);
    backTrack(nums, res, path, visited);
    return res;
};

function backTrack(nums, res, path, visited){
    if(path.length === nums.length) {
        res.push([...path]);
        return;
    }

    for(let i = 0; i< nums.length; i++){
        if(visited[i]) continue;
        if(i>0 && nums[i-1] == nums[i] && !visited[i-1]) continue;
        path.push(nums[i]);
        visited[i] = true;
        backTrack(nums, res, path, visited);
        path.pop();
        visited[i]=false;
    }
}

// 77. 组合
// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
// 你可以按 任何顺序 返回答案。

var combine = function(n, k){
    let res = [];
    let path = [];
    backTrack(n, k, res, path, i)
    return res;
}

function backTrack(n, k, res, path, start){
    if(k === path.length){
        res.push([...path]);
        return
    }
    for(let i = start; i<=n; i++){
        path.push(i);
        backTrack(n, k , res, path, i+1);
        path.pop();
    }
}

var test = function (candidates, target) {
    let res = 0;
    let path = [];
    let sum = 0;
    backtrace(candidates, target, path, 0, sum);
    return res;
    function backtrace(candidates, target, path, index, sum) {
        if (path.length == 2 && sum % target == 0) {
            //     console.log(path);
            res++;
            return;
        } else if (path.length > 2) {
            return;
        }
        for (let i = index; i < candidates.length; i++) {
            path.push(candidates[i]);
            sum += candidates[i];
            backtrace(candidates, target, path, i + 1, sum);
            sum -= candidates[i];
            path.pop();
        }
    }
};


let data = [1, 2, 3, 4, 5, 6];
let res = test(data, 5);
console.log(res);

var list = [['热', '冷', '冰'], ['大', '中', '小'], ["红茶", "绿茶"]];

// 输出所有维度的组合，如 [['热', '冷''], ['大', '中']]  => 热+大，热+中，冷+大，冷+中
function compose(list) {
    console.log('hello world');
    const length = list.length;
    let res = [];
    if (length == 0) return [];
    if (length == 1) return list[0];
    let path = [];

    backTrace(list, path, 0, res);
    return res;
}

function backTrace(list, path, index, res) {
    if (path.length == list.length) {
        res.push(path.join("+"));
        return;
    }
    for (let i = index; i < list.length; i++) {
        for (let j = 0; j < list[index].length; j++) {
            path.push(list[i][j]);
            backTrace(list, path, i + 1, res);
            path.pop(list[i][j]);
        }
    }
}

// let res = compose(list);

// console.log(res);